//#include <iostream>
//
//using namespace std;
//const  int N = 1e5 + 10, MOD = 5000011;
//typedef long long LL;
//LL f[N];
//int main()
//{
//	int n, k; cin >> n >> k;
//
//	for (int i = 1; i <= k + 1; i++)
//	{
//		f[i] = i + 1;
//	}
//	for (int i = k + 2; i <= n; i++)
//	{
//		f[i] = (f[i] + f[i - 1] + f[i - k - 1]) % MOD;
//	}
//	cout << f[n] << endl;
//	return 0;
//}
#include<iostream>
using namespace std;
const int N = 1e5 + 10, MOD = 5000011;
// cn-2 k cmn
// n!
// (n - m)! m!
typedef long long LL;
LL f[N];
LL g[N];
int n, k;
LL qpow(LL a, LL b, LL p)
{
	LL ret = 1;
	while (b)
	{
		if (b & 1) ret = ret * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return ret;
}
void init()
{
	f[0] = 1;
	for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % MOD;

	g[n] = qpow(f[n], MOD - 2, MOD);
	for (int i = n - 1; i >= 0; i--) 
		g[i] = g[i + 1] * (i + 1) % MOD;
}
LL C(int n, int m)
{
	if (n < m) return 0;
	return f[n] * g[n - m] % MOD * g[m] % MOD;
}
int main()
{
	cin >> n >> k;
	init();
	LL ret = 1;
	for (int i = 1; i <= n; i++)
	{
		ret = (ret + C(n - (i - 1) * k, i)) % MOD;
	}
	cout << ret << endl;
	return 0;
}


